class Solution {
public:
    int longestValidParentheses(string s) 
    {
        int n = s.size();
        vector<int> dp(n,0);
        int ret = 0;
        for(int i = 0;i<s.size();i++)
        {
            if(s[i] == ')')
            {
                if(i-1>=0&&i-dp[i-1]-1>=0&&s[i-dp[i-1]-1]=='(')
                {
                    dp[i] = 2+dp[i-1]+(i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0);
                }
            }
            ret = max(ret,dp[i]);
        }
        return ret;
    }
};